package com.fengye.algorithms.leecode;

import com.fengye.algorithms.leecode.common.TreeNode;

/**
 * @Author fengye
 * @Date 2023/4/26 10:09
 **/
public class SubtreeOfAnotherTree572 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3,
                new TreeNode(4, new TreeNode(1), new TreeNode(2,  new TreeNode(0), null)),
                new TreeNode(5));
        TreeNode subTree = new TreeNode(4, new TreeNode(1), new TreeNode(2));
        System.out.println(new SubtreeOfAnotherTree572().isSubtree(root, subTree));
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return dfs(root, subRoot);
    }

    public boolean dfs(TreeNode root, TreeNode subRoot) {
        if(subRoot == null && root == null) {
            return true;
        }

        if(subRoot == null || root == null) {
            return false;
        }
        // 有一个返回true满足条件
        return check(root, subRoot) || dfs(root.left, subRoot) || dfs(root.right, subRoot);
    }

    public boolean check(TreeNode root, TreeNode sub) {
        if(root == null && sub == null) {
            return true;
        }

        if(sub == null || root == null || root.val != sub.val) {
            return false;
        }

        return check(root.left, sub.left) && check(root.right, sub.right);
    }
}
